home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 244_01 / two31.c < prev    next >
Encoding:
C/C++ Source or Header  |  1987-10-24  |  6.3 KB  |  242 lines
  1.  
  2. /* program to analyze the de Bruijn diagram of a cellular */
  3. /* automaton and report all the periodic states. */
  4. /* version for totalistic (3,1), second generation */
  5. /* [Harold V. McIntosh, 4 May 1987] */
  6. /* [10 May 1987 - wait after typing 24 lines] */
  7.  
  8. # include <stdio.h>
  9.  
  10. # define MC     9                /* maximum number of columns */
  11. # define NS      7                /* number of distinct sums */
  12. # define NW    24                /* pause after so many lines */
  13.  
  14. char arry[3][3][3][3][3];            /* all states in the diagram */
  15. int  rule[NS];                    /* transitions by sum value */    
  16. int  nc, nl;                    /* #columns, # lines for print */
  17.  
  18. main() {
  19. int i;
  20.  
  21. printf("Rule number:\n\n");
  22. printf("0..1..2\n");
  23. for (i=0; i<NS; i++) rule[i]=getchar()-'0';
  24. nc=0;
  25. nl=0;
  26.  
  27. kwait(0); printf("Strings conforming to (2,0):"); kwait(0);
  28. pass1a();
  29. pass2i();
  30. pass2o();
  31. pass4();
  32.  
  33. kwait(0); printf("Strings conforming to (2,1):"); kwait(0);
  34. pass1b();
  35. pass2i();
  36. pass2o();
  37. pass4();
  38.  
  39. kwait(0); printf("Strings conforming to (2,2):"); kwait(0);
  40. pass1c();
  41. pass2i();
  42. pass2o();
  43. pass4();
  44.         
  45. } /* end of main */
  46.  
  47. pass1a() {int i0, i1, i2, i3, i4, i, j, k;    /* mark sequences conforming to (2,0) */
  48. printf(" Pass1a\015");
  49. for (i0=0; i0<3; i0++) {
  50. for (i1=0; i1<3; i1++) {
  51. for (i2=0; i2<3; i2++) {
  52. for (i3=0; i3<3; i3++) {
  53. for (i4=0; i4<3; i4++) {
  54. i=rule[i0+i1+i2];
  55. j=rule[i1+i2+i3];
  56. k=rule[i2+i3+i4];
  57. arry[i0][i1][i2][i3][i4]=rule[i+j+k]==i2?'Y':'N';
  58. };};};};};
  59. }
  60.  
  61. pass1b() {int i0, i1, i2, i3, i4, i, j, k;    /* mark sequences conforming to (2,1) */
  62. printf(" Pass1b\015");
  63. for (i0=0; i0<3; i0++) {
  64. for (i1=0; i1<3; i1++) {
  65. for (i2=0; i2<3; i2++) {
  66. for (i3=0; i3<3; i3++) {
  67. for (i4=0; i4<3; i4++) {
  68. i=rule[i0+i1+i2];
  69. j=rule[i1+i2+i3];
  70. k=rule[i2+i3+i4];
  71. arry[i0][i1][i2][i3][i4]=rule[i+j+k]==i1?'Y':'N';
  72. };};};};};
  73. }
  74.  
  75. pass1c() {int i0, i1, i2, i3, i4, i, j, k;    /* mark sequences conforming to (2,2) */
  76. printf(" Pass1c\015");
  77. for (i0=0; i0<3; i0++) {
  78. for (i1=0; i1<3; i1++) {
  79. for (i2=0; i2<3; i2++) {
  80. for (i3=0; i3<3; i3++) {
  81. for (i4=0; i4<3; i4++) {
  82. i=rule[i0+i1+i2];
  83. j=rule[i1+i2+i3];
  84. k=rule[i2+i3+i4];
  85. arry[i0][i1][i2][i3][i4]=rule[i+j+k]==i0?'Y':'N';
  86. };};};};};
  87. }
  88.  
  89. /* Pass2i flags links which have an incoming arrow */
  90. pass2i() {int i0, i1, i2, i3, i4, m;
  91. printf(" Pass2i\015");
  92. do {
  93. for (i0=0; i0<3; i0++) {
  94. for (i1=0; i1<3; i1++) {
  95. for (i2=0; i2<3; i2++) {
  96. for (i3=0; i3<3; i3++) {
  97. for (i4=0; i4<3; i4++) {
  98. if ((arry[i0][i1][i2][i3][i4]&0x5F)=='Y')
  99.  {for (m=0; m<3; m++) arry[i1][i2][i3][i4][m]|=0x20;};
  100. };};};};};
  101. } while (pass3()!=0); }
  102.  
  103. /* Pass2o flags links which have an outgoing arrow */
  104. pass2o() {int i0, i1, i2, i3, i4, m;
  105. do {
  106. printf(" Pass2o\015");
  107. for (i0=0; i0<3; i0++) {
  108. for (i1=0; i1<3; i1++) {
  109. for (i2=0; i2<3; i2++) {
  110. for (i3=0; i3<3; i3++) {
  111. for (i4=0; i4<3; i4++) {
  112. if ((arry[i0][i1][i2][i3][i4]&0x5F)=='Y')
  113.  {for (m=0; m<3; m++) arry[m][i0][i1][i2][i3]|=0x20;};
  114. };};};};};
  115. } while (pass3()!=0); }
  116.  
  117. /* printf("pass3 - erase flags, mark survivors, count channges\n"); */
  118. int pass3() {int i0, i1, i2, i3, i4, l;    /* mark states still linked */
  119. printf(" Pass3\015");
  120. l=0;
  121. for (i0=0; i0<3; i0++) {
  122. for (i1=0; i1<3; i1++) {
  123. for (i2=0; i2<3; i2++) {
  124. for (i3=0; i3<3; i3++) {
  125. for (i4=0; i4<3; i4++) {
  126. switch (arry[i0][i1][i2][i3][i4]) {
  127.     case 'y': arry[i0][i1][i2][i3][i4]='Y'; break;
  128.     case 'Y': arry[i0][i1][i2][i3][i4]='N'; l=1; break;
  129.     case 'n': case 'N': arry[i0][i1][i2][i3][i4]='N'; break;
  130.     default: break; };
  131. };};};};};
  132. return l;
  133. }
  134.  
  135. /* pass4 - print loops which remain */
  136. pass4() {
  137. int i0, i1, i2, i3, i4;
  138. int j0, j1, j2, j3, j4, k, l, m;
  139. printf(" pass4 \015");
  140. for (i0=0; i0<3; i0++) {
  141. for (i1=0; i1<3; i1++) {
  142. for (i2=0; i2<3; i2++) {
  143. for (i3=0; i3<3; i3++) {
  144. for (i4=0; i4<3; i4++) {
  145. j1=i1; j2=i2; j3=i3; j4=i4; l=0; m=0;
  146. do {
  147.         if (arry[0][j1][j2][j3][j4]=='Y')
  148.     {arry[0][j1][j2][j3][j4]='y';
  149.     k=j4; j4=j3; j3=j2; j2=j1; j1=0; m=1;}
  150.   else {if (arry[1][j1][j2][j3][j4]=='Y')
  151.     {arry[1][j1][j2][j3][j4]='y';
  152.     k=j4; j4=j3; j3=j2; j2=j1; j1=1; m=1;}
  153.   else {if (arry[2][j1][j2][j3][j4]=='Y')
  154.     {arry[2][j1][j2][j3][j4]='y';
  155.     k=j4; j4=j3; j3=j2; j2=j1; j1=2; m=1;}
  156.   else {l=1; if (m==1) {j0=j1; j1=j2; j2=j3; j3=j4; j4=k;}; };};};
  157.   } while (l==0);
  158. l=0; 
  159. m=0;
  160. do {
  161.         if (arry[j0][j1][j2][j3][0]=='y')
  162.    {prf(j0,j1,j2,j3,0);
  163.    arry[j0][j1][j2][j3][0]='N';
  164.    j0=j1; j1=j2; j2=j3; j3=0; m=1;}
  165.   else {if (arry[j0][j1][j2][j3][1]=='y')
  166.    {prf(j0,j1,j2,j3,1);
  167.    arry[j0][j1][j2][j3][1]='N';
  168.    j0=j1; j1=j2; j2=j3; j3=1; m=1;}
  169.   else {if (arry[j0][j1][j2][j3][2]=='y')
  170.    {prf(j0,j1,j2,j3,2);
  171.    arry[j0][j1][j2][j3][2]='N';
  172.    j0=j1; j1=j2; j2=j3; j3=2; m=1;}
  173.   else {l=1;};};};
  174.   } while (l==0);
  175. l=0;
  176. do {
  177.         if (arry[j0][j1][j2][j3][0]=='Y')
  178.    {prf(j0,j1,j2,j3,0);
  179.    arry[j0][j1][j2][j3][0]='N';
  180.    j0=j1; j1=j2; j2=j3; j3=0; m=1;}
  181.   else {if (arry[j0][j1][j2][j3][1]=='Y')
  182.    {prf(j0,j1,j2,j3,1);
  183.    arry[j0][j1][j2][j3][1]='N';
  184.    j0=j1; j1=j2; j2=j3; j3=1; m=1;}
  185.   else {if (arry[j0][j1][j2][j3][2]=='Y')
  186.    {prf(j0,j1,j2,j3,2);
  187.    arry[j0][j1][j2][j3][2]='N';
  188.    j0=j1; j1=j2; j2=j3; j3=2; m=1;}
  189.   else {l=1; if (m==1) {kwait(0);} ;};};};
  190.   } while (l==0);
  191. };};};};};
  192. }
  193.  
  194. /* print one of the links in a chain */
  195. prf(i0,i1,i2,i3,i4) int i0, i1,i2, i3, i4; {
  196. kwait(1);
  197. printf("%1d",i0);
  198. printf("%1d",i1);
  199. printf("%1d",i2);
  200. printf("%1d",i3);
  201. printf("-");
  202. printf("%1d",i4);
  203. printf("  ");}
  204.  
  205. /* print the whole list of links */
  206. pall() {
  207. int i0, i1, i2, i3, i4;
  208. for (i0=0; i0<3; i0++) {
  209. for (i1=0; i1<3; i1++) {
  210. for (i2=0; i2<3; i2++) {
  211. for (i3=0; i3<3; i3++) {
  212. for (i4=0; i4<3; i4++) {
  213. printf("%c",arry[i0][i1][i2][i3][i4]);
  214. };};};};};
  215. printf("\n");
  216. }
  217.  
  218. /* keyboard status */
  219. kbdst() {return bdos(11)&0xFF;}
  220.  
  221. /* direct keyboard input, no echo */
  222. kbdin() {int c;
  223. if ((c=bdos(7)&0xFF)=='\0') c=(bdos(7)&0xFF)|0x80;
  224. return c;}
  225.  
  226. /* pause at the end of a full screen */
  227. kwait(i) int i; {
  228. switch (i) {
  229.   case 0: printf("\n"); nc=0; nl++; break;
  230.   case 1: if (nc==MC) {printf("&\n"); nc=1; nl++;} else nc++; break;
  231.   default: break;};
  232. if (nl==NW) {
  233.   nl=0;
  234.   printf(" press any key to continue\015");
  235.   while (kbdst()) {};
  236.   kbdin();
  237.   printf("-                         \n");
  238.   };
  239. }
  240.  
  241. /* end */
  242.